import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description：
 * User：user
 * DATE:2021-11-09
 * Time:22:16
 */
class TreeNode{
    public  char val;
    public  TreeNode left;
    public  TreeNode right;
    public  TreeNode(char val){
        this.val = left.val;
    }
}
public class TestBinaryTree {

    // 前序遍历
    void preOrderTraversal(TreeNode root){
        if(root == null)return;
        TreeNode cur = root;
        TreeNode top = null;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            top = stack.pop();
            cur = top.right;
        }
    }
    // 中序遍历
    void inOrderTraversal(TreeNode root){
        if(root == null)return;
        TreeNode cur = root;
        TreeNode top = null;
        Stack<TreeNode> stack = new Stack<>();

        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            top = stack.pop();
            System.out.print(top.val + " ");
            top = top.right;
        }
        System.out.println();

    }
    public TreeNode prev = null;
    // 后序遍历
    void postOrderTraversal(TreeNode root){
        if(root == null)return;
        TreeNode cur = root;
        TreeNode top = null;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            cur  = stack.peek();
            if(cur.right == null || cur.right == prev){
                cur = stack.pop();
                System.out.print(cur.val + " ");
                prev = cur;
                cur = null;
            }else{
                cur = cur.right;
            }
        }
        System.out.println();
    }
}
